package com.fanshuai.algorithms.backtrack;

import com.fanshuai.algorithms.datastructure.graph.IndirectGraph;
import com.fanshuai.algorithms.datastructure.tree.binarytree.IntListValue;
import com.fanshuai.algorithms.datastructure.tree.binarytree.IntValue;

import java.util.ArrayList;
import java.util.List;

/**
 * 一销售商从n个城市中的某一城市出发，不重复地走完其余n—1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条
 * n个城市构成一个图，使用邻接矩阵matrix表示图，matrix[i][j]表示城市i到j的距离
 * 使用BFS来遍历图，从src原点开始，知道某个节点的邻接节点中有src，通过回溯法计算最短路径
 *
 * 限界条件1：!path.Contains(i)
 * 限界条件2：pathSum + matrix[cur][i] < minPathSum.value
 */
public class Travel {
    /**
     * 陆行赏问题
     * @param matrix 图的邻接矩阵
     * @param src 出发点城市
     * @return
     */
    public static List<Integer> minCyclePath(int[][] matrix, int src) {
        IntListValue minPath = new IntListValue();
        List<Integer> path = new ArrayList<>();
        IntValue minPathSum = new IntValue(Integer.MAX_VALUE);

        path.add(src);
        minCyclePath0(matrix, src, src,0, minPathSum, path, minPath);

        System.out.println("minPath=" + minPathSum.value);
        return minPath.listValue;
    }

    private static void minCyclePath0(int[][] matrix, int src, int cur, int pathSum, IntValue minPathSum, List<Integer>
            path, IntListValue minPath) {

        int n = matrix.length - 1;
        /**
         * 递归层数到达n层时，说明走过全部城市，计算最小路径
         */
        if (path.size() == n) {
            int last = path.get(path.size() - 1);

            if (matrix[last][src] < Integer.MAX_VALUE && matrix[last][src] + pathSum < minPathSum.value) {
                minPathSum.value = matrix[last][src] + pathSum;
                minPath.listValue = new ArrayList<>(path);
                minPath.listValue.add(src);
            }

            return;
        }

        for (int i = 1; i <= n; i++) {
            /**
             * for循环有限制条件，保证递归层数小于5层时，不符合条件的不向下递归，直接返回。例如某些节点并非与全部节点相连，这时通过连通性和限界函数限制
             * path.Contains只保证不重复，可以最优化
             * 限界条件1：!path.Contains(i)
             * 限界条件2：pathSum + matrix[cur][i] < minPathSum.value
             */
            boolean validSubTree = !path.contains(i) && pathSum + matrix[cur][i] < minPathSum.value;
            if (matrix[cur][i] < Integer.MAX_VALUE && validSubTree) {
                path.add(i);
                minCyclePath0(matrix, src, i, pathSum + matrix[cur][i], minPathSum, path, minPath);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[][] a1 = new int[][] {{1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {2, 5, 3}, {3, 4, 5},
                {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 6}};

        int[][] a2 = new int[][] {{1, 2, 3}, {1, 4, 8}, {1, 5, 9}, {2, 3, 3}, {2, 4, 10},
                {2, 5, 5}, {3, 4, 4}, {3, 5, 3}, {4, 5, 20}};

        IndirectGraph<Integer> graph = new IndirectGraph<>(6);
        for (int[] i : a1) {
            graph.addEdge(i[0], i[1], i[2]);
        }
        System.out.println(minCyclePath(graph.getMatrix(), 1));

        IndirectGraph<Integer> graph2 = new IndirectGraph<>(5);
        for (int[] i : a2) {
            graph2.addEdge(i[0], i[1], i[2]);
        }
        System.out.println(minCyclePath(graph2.getMatrix(), 1));
    }

}
